A mobile ad hoc network (MANET) is a wireless network that includes a collection of nodes whose positions and participation in the network are continually changing. Unlike conventional wired and wireless networks, a MANET does not rely on fixed infrastructure. Instead, most or all the nodes of a MANET function as routers. MANETs can be important in many situations such as during natural disasters and on the battlefield because they do not require fixed infrastructure and are typically more fault-tolerant than infrastructure-based networks. For example, a cell tower that covers a large number of nodes can represent a single point of failure—if the cell tower goes down, so does its coverage area. In contrast, if one node in MANET goes down, the rest of the network is generally not affected because traffic can be rerouted via the rest of the nodes. A MANET on the battlefield may include nodes such as a rearward command center, mobile communicators carried by individual soldiers, land vehicles, aircraft, semi-permanent base or relay stations, randomly placed sensors with radio communication (e.g., motion detectors air dropped into forward areas), and scattered relay nodes.
As described in U.S. Pat. No. 7,957,355 (incorporated herein by reference in its entirety), devices in a MANET (nodes) may be randomly-placed, may move about unpredictably, and may enter or leave the network at any time. Typically, the broadcasting range of a node in a MANET is only a fraction of the overall network size. Thus, for information to be sent from a first node to another node outside of the first node's range, the packet must “hop” through one or more intermediate nodes. For example, referring to FIG. 1, MANET nodes generally communicate information by relaying a data “packet” from a source node 110 to a destination node 115 by hopping through intermediate nodes 122, 124, and 126, since destination node 115 may not be within the broadcast range of source node 110. For example, source node 110 has a broadcast range 140 that does not reach the desired destination node 115, but does reach neighbor node 122, which would be the first intermediate node for routing a data packet from source node 110 to destination node 115. Likewise, second intermediate node 124 is within the first intermediate node's broadcast range 142; third intermediate node 126 is within the second intermediate node's broadcast range 144; and finally the destination node 115 is within the third intermediate node's broadcast range 146.
The network topology illustrated in FIG. 1 would not likely remain for long in a real scenario because the mobility of the nodes causes frequent changes in network topology. This varying network topology causes difficulty in applying routing techniques used in conventional wired or wireless networks. Conventional MANET routing protocols are topology-based protocols that evolved from the wired world. Topology-based MANET routing protocols are broadly categorized into two main groups: proactive and reactive. In a reactive protocol, routes have to be discovered on demand before they can be used, which incurs a discovery delay, thereby increasing latency, which may not be acceptable in certain applications. In a proactive, or table-driven protocol, the routes to all destinations within the network are disseminated and maintained before use. The advantage of the proactive protocols is that the requested route is available immediately whereas in reactive protocols the route may need to be discovered first.
Conventional networks typically employ proactive routing protocols. The nodes in a conventional network are stationary, and the links connecting the nodes go down infrequently. As such, it is possible to maintain the whole network topology at each node by sending topology-related information to all the nodes in the network via “link-state” updates. Since nodes go down infrequently, link-state updates are infrequent. However, in a MANET, link-state changes are more frequent because of the shifting topology, thus requiring many more link-state update messages to be propagated throughout the MANET, consuming valuable bandwidth in the process.
One of the key challenges in MANETS, then, is that the amount of routing control overhead can consume a large portion of the limited available bandwidth, which is known in the art as the broadcast storm problem. This problem is especially acute in dense deployment scenarios where a good portion of the nodes are one-hop away from each other (are neighbor nodes) and the rest are two and more hops away. The size of the routing control packets in these scenarios can be quite large because each node has a large number of one-hop neighbors and each of these hops needs to be described in each routing control packet. Dense or moderately dense scenarios arise often in real life as nodes tend to form dense clusters.
Therefore, it is desirable to minimize the amount of routing control overhead needed for route maintenance in a proactive routing protocol for a MANET.